import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode : 78. 子集
 * <a href="https://leetcode.cn/problems/subsets/">...</a>
 * User: DELL
 * Date: 2023-07-13
 * Time: 12:58
 */
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 判空处理
        if (nums == null || nums.length == 0) {
            return res;
        }
        // 因为数组中元素互不相同,因此这里不用对原数组进行排序
        // 而若有重复元素,则需要对原数组进行排序,并且在dfs时候
        // 加上判断条件避免重复
        Deque<Integer> temp = new LinkedList<>();
        dfs(res,nums,0,temp);
        return res;
    }

    /**
     * dfs 遍历所有情况
     * @param res     存储遍历结果
     * @param nums    元素数组
     * @param index   当前遍历到的元素的下标
     * @param temp    临时记录已经选取的元素
     */
    private void dfs( List<List<Integer>> res, int[] nums, int index, Deque<Integer> temp) {
        if (index == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        // 1. 不包含当前元素
        dfs(res,nums,index+1,temp);
        // 2. 包含当前元素
        temp.add(nums[index]);
        dfs(res,nums,index+1,temp);
        // 回溯
        temp.removeLast();
    }
}